Dijkstra's Algorithm is a foundational greedy method used to find the shortest paths from a single source vertex in a weighted graph.
- Developed by Edsger W. Dijkstra in 1956, it is one of the most famous graph algorithms.
- It solves the Single-Source Shortest Path (SSSP) problem, finding the shortest path from a source $s$ to all other nodes.
- The algorithm is greedy: at each step, it selects the unvisited vertex with the smallest known distance from the source.
- A critical requirement is that all edge weights must be non-negative ($w(u, v) \ge 0$).
- If negative weights were allowed, the greedy choice might become incorrect later, requiring a different algorithm (like Bellman-Ford).
- The final result is a Shortest Path Tree rooted at the source vertex $s$.
Algorithm Summary
| Algorithm | Problem Solved | Key Constraint |
|---|---|---|
| Dijkstra's | Single-Source Shortest Path (SSSP) | All edge weights must be non-negative ($\ge 0$) |